前言

今天帶三題題目，希望大家可以經過這三題的練習更加瞭解排序演算法與在競賽、解題中的使用

UVa 10327 - Flip Sort

題目說明

白話來說就是要求氣泡排序完數列最少需要交換幾次

解題思路

由於題目的數列長度 最大只會是 ，因此直接做氣泡排序求出交換次數也可以過

時間複雜度

AC Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        int arr[n + 10],ans = 0;
        for(int i = 0;i < n;i++){
            cin >> arr[i];
        }
        for(int i = 0;i < n - 1;i++){
            for(int j = 0;j + 1 < n;j++){
                if(arr[j] > arr[j + 1]){
                    swap(arr[j],arr[j + 1]);
                    ans++;
                }
            }
        }
        cout << "Minimum exchange operations : " << ans << "\n";
    }
    return 0;
}

UVa 11321 - Sort! Sort!! and Sort!!!

題目說明

基本上就是依照題目規則做排序，規則在以下做整理：

1. 利用每個數字除以 的餘數由小到大排
2. 除以 的餘數相等，且比較的兩數為一奇一偶，則奇數要排在偶數前面
3. 兩奇數除以 餘數大小相等，則原本數值較大的奇數排在前面
4. 兩偶數除以 餘數大小相等，則較小的偶數排在前面

注意

負數的餘數計算和 C 語言裡的定義相同，即負數的餘數絕對不會大於零。例如 -100 MOD 3 = -1, -100 MOD 4 = 0 依此類推。

解題思路

可以利用 C++ 內建的排序函式並搭配比較函式直接排序

時間複雜度

AC Code

#include <bits/stdc++.h>
using namespace std;
long long n,m;
bool cmp(long long a,long long b){
    if(a % m != b % m){
        return a % m < b % m;
    }else{
        if(abs(a) % 2 != abs(b) % 2){
            return abs(a) % 2 > abs(b) % 2;
        }else{
            return abs(a) % 2 ? a > b : a < b;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n >> m && n && m){
    	cout << n << " " << m << "\n";
    	vector<long long> v(n);
    	for(auto &i : v){
    		cin >> i;
    	}
    	sort(v.begin(),v.end(),cmp);
    	for(auto &i : v){
            cout << i << "\n";
    	}
    }
    cout << n << " " << m << "\n";
    return 0;
}

2193 . A. 原始人排序

題目說明

本題是 2021 TOI 初選大家公認的簡單題，而這題剛好可以讓大家了解 sort 穩不穩定的區別，題目要讓大家將數列依照二進位中 的數量由小到大排序，而如果數量相同就依照輸入順序排序

解題思路

可以發現它需要用到二進位中 的數量，所以在此題我使用 pair 來存數值和該數值的二進位中 的數量，而計算二進位中 的數量我使用 __builtin_popcount() 函式，可以直接取得數量，接下來在寫比較函式，並且因為他如果數量相同會需要依照輸入順序排序，因此須注意要使用 stable_sort()

時間複雜度

AC Code

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<long long,long long> a,pair<long long,long long> b){
    return a.second < b.second;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    vector<pair<long long,long long>> v(n);
    for(int i = 0;i < n;i++){
        cin >> v[i].first;
        v[i].second = __builtin_popcount(v[i].first);
    }
    stable_sort(v.begin(),v.end(),cmp);
    for(auto &[i,j] : v){
        cout << i << " ";
    }
    cout << "\n";
    return 0;
}

總結

可以看到有些的題目其實可以使用內建函式就好，不過還是得需要了解它的原理以及如何實作，並進而瞭解時間複雜度，才不會造成誤用或是錯估時間複雜度

預告

明天還在思考要講貪心、二分搜還是簡單的 DFS、BFS，不過一樣會是分成講概念 + 帶幾題練習題，大家可以期待一下，或是敲碗要看什麼內容